package Tree;

import javax.swing.tree.TreeNode;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Tree1 {
    //漫画算法  第三章   树
    //二叉树的遍历方式：前中后序

    //二叉树节点
    public static class TreeNode{
        int data ; //节点
        TreeNode leftChild ; //左孩子
        TreeNode rightChild ; //右孩子

        TreeNode(int data){
            this.data = data ;
        }
    }


    //构建二叉树
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
        TreeNode node = null;
        if (inputList == null ||inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst() ;
        if(data != null){
            node = new TreeNode(data) ;
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList) ;
        }
        return node;
    }

    //前序遍历  根左右
    public static void preOrder (TreeNode node){
        if (node == null){
            return;
        }
        System.out.println(node.data);
        preOrder(node.leftChild);
        preOrder(node.rightChild);
    }


    //中序遍历 左根右
    public static void InOrder (TreeNode node){
        if (node == null){
            return;
        }
        InOrder(node.leftChild);
        System.out.println(node.data);
        InOrder(node.rightChild);
    }
    //后序遍历  左右根
    public static void Postorder (TreeNode node){
        if (node == null){
            return;
        }
        Postorder(node.leftChild);
        Postorder(node.rightChild);
        System.out.println(node.data);
    }

    //层序遍历
    public static void Sequence(TreeNode node){
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(node);
        while (!queue.isEmpty()){
            node = queue.poll();
            System.out.println(node.data);
            if(node.leftChild != null){
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null){
                queue.offer(node.rightChild);
            }
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3, 9, 2, null, null, 10, null, null, 8, 6, 4}));
        TreeNode treeNode = createBinaryTree(inputList);
        System.out.println("前序遍历:");
        preOrder(treeNode);
        System.out.println("中序遍历:");
        InOrder(treeNode);
        System.out.println("后序遍历:");
        Postorder(treeNode);
    }
}
